﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NumberPuzzle
{
    class PuzzleSolver
    {
        public static int nodeCount = 0;
        static List<node> priorityQueue = new List<node>();
        static int[] backTrackParent = new int[100000];
        static int[,] backTrackMove = new int[100000, 2];

        static node actualPuzzle = new node(0, 0);
        static node expectedPuzzle = new node(0, 0);
        static NodeComparer nc = new NodeComparer();

        static void ShowPuzzle(ref node n)
        {
            Console.WriteLine("+--------------+");
            for (int i = 0; i < n.pstate.GetLength(0); i++)
            {
                Console.Write("|");
                for (int j = 0; j < n.pstate.GetLength(0); j++)
                {
                    if (n.pstate[i, j] == n.pstate.GetLength(0) * n.pstate.GetLength(1)) Console.Write("    |");
                    else Console.Write(" {0,2:D} |", n.pstate[i, j]);
                }
                Console.WriteLine();
                Console.WriteLine("+--------------+");
            }
        }

        static void CalculateHeuristics(ref node act, ref node exp)
        {
            int h1_calc = 0; // Manhattan Distance
            int h2_calc = 0; // Misplaced tiles
            int[,] actxy = new int[16, 2];
            int[,] expxy = new int[16, 2];

            for (int i = 0; i < act.pstate.GetLength(0); i++)
                for (int j = 0; j < act.pstate.GetLength(1); j++)
                {
                    int tile_number = act.pstate[i, j] - 1;
                    actxy[tile_number, 0] = i;
                    actxy[tile_number, 1] = j;
                }

            for (int i = 0; i < exp.pstate.GetLength(0); i++)
                for (int j = 0; j < exp.pstate.GetLength(1); j++)
                    if ((i + 1) * (j + 1) < exp.pstate.GetLength(0) * exp.pstate.GetLength(1)) // Do not calculate for empty space
                    {
                        int tile_number = exp.pstate[i, j] - 1;
                        expxy[tile_number, 0] = i;
                        expxy[tile_number, 1] = j;

                        int md = Math.Abs(expxy[tile_number, 0] - actxy[tile_number, 0]) + Math.Abs(expxy[tile_number, 1] - actxy[tile_number, 1]);
                        h1_calc += md;
                        if (md == 0) h2_calc++;
                    }

            // Linear Conflict
            for (int i = 0; i < act.pstate.GetLength(0); i++)
                for (int j = 0; j < act.pstate.GetLength(1); j++)
                {
                    int tile_number = act.pstate[i, j] - 1;
                    if (tile_number >= act.pstate.GetLength(0) * act.pstate.GetLength(1) - 1) continue;

                    int md = Math.Abs(expxy[tile_number, 0] - actxy[tile_number, 0]) + Math.Abs(expxy[tile_number, 1] - actxy[tile_number, 1]);
                    if (md == 1)
                    {
                        int tileInDest_Number = act.pstate[expxy[tile_number, 0], expxy[tile_number, 1]] - 1;
                        if (tileInDest_Number >= act.pstate.GetLength(0) * act.pstate.GetLength(1) - 1) continue;
                        int tileInDestDest_Number = act.pstate[expxy[tileInDest_Number, 0], expxy[tileInDest_Number, 1]] - 1;

                        if (tile_number == tileInDestDest_Number) // Linear conflict found
                        {
                            h1_calc++;
                        }
                    }
                }

            act.h1_ManDis = h1_calc;
            act.h2_MisTiles = act.pstate.GetLength(0) * act.pstate.GetLength(1) - h2_calc;
        }

        static int AStarSearch()
        {
            node local = new node(0, 0);
            int[,] moves = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

            while (priorityQueue.Count > 0)
            {
                // Get the first node
                node n = new node(priorityQueue[0]);
                // Remove first element
                priorityQueue.RemoveAt(0);

                if (n.h1_ManDis == 0)
                {
                    Console.WriteLine("MOVES = " + n.moves);
                    return n.id; // Solution found. Return solution node id
                }

                // Expand the node
                for (int i = 0; i < moves.GetLength(0); i++)
                {
                    int newsx = n.sx + moves[i, 0];
                    int newsy = n.sy + moves[i, 1];

                    if (i == (n.lastMoveDir + 2) % 4) continue;

                    if ((newsx >= 0 && newsx < n.pstate.GetLength(0)) & (newsy >= 0 && newsy < n.pstate.GetLength(1)))
                    {
                        local = new node(n);

                        local.id = nodeCount;
                        local.parent = n.id;
                        ++nodeCount;

                        // Record back tracks
                        backTrackMove[local.id, 0] = newsx;
                        backTrackMove[local.id, 1] = newsy;
                        backTrackParent[local.id] = local.parent;

                        // Swap values
                        int tmp = local.pstate[n.sx, n.sy];
                        local.pstate[n.sx, n.sy] = local.pstate[newsx, newsy];
                        local.pstate[newsx, newsy] = tmp;

                        local.sx = newsx;
                        local.sy = newsy;
                        local.lastMoveDir = i;
                        local.moves++;
                        CalculateHeuristics(ref local, ref expectedPuzzle);
                        Push(local);
                    }
                }
            } // While

            return -1;
        }

        static void Push(node n)
        {
            int pos = priorityQueue.BinarySearch(n, nc);
            if (pos < 0) pos = (-pos) - 1;

            if (pos > priorityQueue.Count || priorityQueue.Count == 0) priorityQueue.Add(n);
            else priorityQueue.Insert(pos, n);
        }

        public static List<int> SolvePuzzle(int[,] inputPuzzle)
        {
            // Initialize static elements
            nodeCount = 0;
            priorityQueue.Clear();

            // Initialize actual node
            actualPuzzle = new node(ref inputPuzzle, 0, 0, 0, 0, 0);
            actualPuzzle.id = nodeCount;
            ++nodeCount;

            // Initialize expected node
            int[,] exp = new int[,] { {1,2,3},
                                      {4,5,6},
                                      {7,8,9} };
            expectedPuzzle = new node(ref exp, 0, 0, 0, 2, 2);

            // Calculate actual and expected heuristics
            CalculateHeuristics(ref actualPuzzle, ref expectedPuzzle);
            CalculateHeuristics(ref expectedPuzzle, ref expectedPuzzle);

            // Add first node to the queue
            Push(actualPuzzle);

            // Start A* Search
            int solutionNodeID = AStarSearch();

            // List of moves to the solution
            List<int> movesToSolve = new List<int>();

            // No solution found
            if (solutionNodeID < 0) return movesToSolve;

            // Backtrack an return solution
            int bt_id = solutionNodeID;
            int bt_par = backTrackParent[solutionNodeID];
            while (bt_id > 0)
            {
                //Console.WriteLine(backTrackMove[bt_id, 0] + ", " + backTrackMove[bt_id, 1]);
                movesToSolve.Insert(0, backTrackMove[bt_id, 1]);
                movesToSolve.Insert(0, backTrackMove[bt_id, 0]);
                bt_id = bt_par;
                bt_par = backTrackParent[bt_id];
            }

            return movesToSolve;
        }

        public class NodeComparer : IComparer<node>
        {
            public int Compare(node x, node y)
            {
                if (x.f1 < y.f1) return -1;
                if (x.f1 == y.f1) return 0;
                //{
                //    if (x.f2 < y.f2) return -1;
                //    if (x.f2 == y.f2) return 0;
                //}
                return 1;
            }
        }
    }

    class node
    {
        public int id;
        public int parent;
        private int[,] _pstate;
        private int _f1;
        private int _f2;
        private int _moves;
        private int _h1_ManDis;
        private int _h2_MisTiles;
        public int sx;
        public int sy;
        public int lastMoveDir;

        public node(int csx, int csy)
        {
            id = -1; parent = -1;
            _pstate = new int[3, 3];
            _f1 = 0;
            _f2 = 0;
            _moves = 0;
            _h1_ManDis = 0;
            _h2_MisTiles = 0;
            sx = csx;
            sy = csy;
            lastMoveDir = -1;
        }

        public node(int cmoves, int ch1_MD, int ch2_MT, int csx, int csy, int clast = -1)
        {
            id = -1; parent = -1;
            _pstate = new int[3, 3];
            _moves = cmoves;
            _h1_ManDis = ch1_MD;
            _h2_MisTiles = ch2_MT;
            _f1 = _moves + _h1_ManDis;
            _f2 = _moves + _h2_MisTiles;
            sx = csx;
            sy = csy;
            lastMoveDir = clast;
        }

        public node(ref int[,] puzzle, int cmoves, int ch1_MD, int ch2_MT, int csx, int csy, int clast = -1)
        {
            id = -1; parent = -1;
            _moves = cmoves;
            _h1_ManDis = ch1_MD;
            _h2_MisTiles = ch2_MT;
            _f1 = _moves + _h1_ManDis;
            _f2 = _moves + _h2_MisTiles;
            sx = csx;
            sy = csy;
            lastMoveDir = clast;

            _pstate = new int[3, 3];
            setPuzzle(ref puzzle);
        }

        public node(node cn)
        {
            id = cn.id; parent = cn.parent;
            _moves = cn.moves;
            _h1_ManDis = cn.h1_ManDis;
            _h2_MisTiles = cn.h2_MisTiles;
            _f1 = _moves + _h1_ManDis;
            _f2 = _moves + _h2_MisTiles;
            sx = cn.sx;
            sy = cn.sy;
            lastMoveDir = cn.lastMoveDir;

            _pstate = new int[3, 3];
            setPuzzle(ref cn);
        }

        public void setPuzzle(ref int[,] puzzle)
        {
            for (int i = 0; i < _pstate.GetLength(0); i++)
                for (int j = 0; j < _pstate.GetLength(1); j++)
                {
                    _pstate[i, j] = puzzle[i, j];
                    if (_pstate[i, j] == _pstate.GetLength(0) * _pstate.GetLength(1)) // Set no tile coordinates
                    {
                        this.sx = i;
                        this.sy = j;
                    }
                }
        }

        public void setPuzzle(ref node n)
        {
            for (int i = 0; i < _pstate.GetLength(0); i++)
                for (int j = 0; j < _pstate.GetLength(1); j++)
                {
                    _pstate[i, j] = n.pstate[i, j];
                    if (_pstate[i, j] == _pstate.GetLength(0) * _pstate.GetLength(1)) // Set no tile coordinates
                    {
                        this.sx = i;
                        this.sy = j;
                    }
                }
        }

        public int[,] pstate
        {
            get { return this._pstate; }
        }

        public int f1
        {
            get { return this._f1; }
        }

        public int f2
        {
            get { return this._f2; }
        }

        public int moves
        {
            set { this._moves = value; _f1 = _moves + _h1_ManDis; _f2 = _moves + _h2_MisTiles; }
            get { return this._moves; }
        }

        public int h1_ManDis
        {
            set { this._h1_ManDis = value; _f1 = _moves + _h1_ManDis; }
            get { return this._h1_ManDis; }
        }

        public int h2_MisTiles
        {
            set { this._h2_MisTiles = value; _f2 = _moves + _h2_MisTiles; }
            get { return this._h2_MisTiles; }
        }

    }
}
